/*
提交链接：https://leetcode.cn/problems/number-of-provinces/submissions/573450725
547. 省份数量-中等
完成日期：2024/10/17
并查集
*/

class UnionFind {
public:
    UnionFind(int size) {
        parent.resize(size);
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始化每个城市的父节点为自己
        }
    }
    int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]); // 路径压缩
        }
        return parent[node];
    }
    void unionNodes(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            parent[rootU] = rootV; // 合并两个城市
        }
    }
private:
    vector<int> parent; // 存储每个城市的父节点
};
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        UnionFind uf(n); // 初始化并查集
        // 合并直接相连的城市
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.unionNodes(i, j); // 合并城市 i 和城市 j
                }
            }
        }
        // 计算省份的数量
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (uf.find(i) == i) {
                provinces++; // 每找到一个独立根节点，省份数量加 1
            }
        }
        return provinces;
    }
};